/**
 *
 * @description 利用二叉搜索树的特性
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  const list = [];
  const postOrder = (node) => {
    if (!node) {
      return;
    }
    postOrder(node.left);
    postOrder(node.right);
    list.push(node.val);
  };
  postOrder(root);
  return list.join(' ');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  if (!data) {
    return null;
  }
  const list = data.split(' ').map((str) => parseInt(str));
  const recurse = (arr) => {
    if (!arr.length) {
      return null;
    }
    const num = arr.pop();
    const treeNode = new TreeNode(num);
    //! 这里多了一次循环遍历
    treeNode.left = recurse(arr.filter((item) => item < num));
    treeNode.right = recurse(arr.filter((item) => item > num));
    return treeNode;
  };

  return recurse(list);
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
